package com.atwy.tree;

import java.util.Arrays;

/**
 * 堆：可以被看作一棵树的数组对象，满足以下性质：
 * 1.堆中某个结点的值总是不大于或不小于其父结点的值；
 * 2.堆总是一个完全二叉树
 * <p>
 * 根结点是最大值的是大顶堆，根结点是最小值的是小顶锥。
 * <p>
 * n个元素的数组array，满足 array[i]<=array[2i] && array[i]<=array[2i+1]，（或者）
 * array[i]>=array[2i] && array[i]>=array[2i+1],就是堆。
 * <p>
 * 堆的根结点要么是最大值，要么是最小值。堆的这属性非常有用，因为堆常常被当做优先队列使用，因为可以快速地访问到最重要的元素。
 * <p>
 * 堆的应用，堆排序
 * 堆排序的基本思想是：
 * 1) 将待排序序列构造成一个大顶堆
 * 2) 此时，整个序列的最大值就是堆顶的根节点。
 * 3) 将其与末尾元素进行交换，此时末尾就为最大值。
 * 4) 然后将剩余 n-1 个元素重新构造成一个大顶堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序 序列了。
 *
 * 堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。
 * 例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。
 * --唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。
 *
 */
public class HeapSortDemo {
    public static void main(String[] args) {
        int[] array = {4, 6, 8, 5, 9, 3, 2};
        System.out.println("原数组：" + Arrays.toString(array));
        //adjustHeap(array,0,array.length);
        int len = array.length;
        //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
        // ****从最后一个非叶子结点开始，最后一个**非叶子结点 i=len/2 -1
        // ****首先i结点的子结点是 2*i+1，2*i+2,存在关系（2*i+1 = len-1,或者2*i+2 = len-1）,推出i = len/2 -1
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, len);
        }
        System.out.println("大顶堆：" + Arrays.toString(array));
        int temp = 0;
        // 对大顶堆就行调整，将顶与数组末尾交换
        for (int j = len - 1; j > 0; j--) {
            temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            // 最大值放在末尾后，数组长度减一，继续做调整
            adjustHeap(array, 0, j);
        }
        System.out.println("排好序：" + Arrays.toString(array));


        int[] array2 = {4, 6, 8, 5, 9, 3, 2};
        sort(array2);
        System.out.println("案例二：" + Arrays.toString(array2));

    }

    public static void sort(int[] array) {
        int len = array.length;

        //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
        // 从最后一个非叶子结点开始，最后一个**非叶子结点 i=len/2 -1
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, len);
        }
        int temp = 0;
        // 对大顶堆进行调整，将顶与数组末尾交换
        for (int j = len - 1; j > 0; j--) {
            swap(array,0,j);
            // 最大值放在末尾后，数组长度减一，继续做调整
            adjustHeap(array, 0, j);
        }
    }

    /**
     * 将一个数组（二叉树），调整成一个大顶堆
     * 从简单的模型进行思考，假设有三个节点，父节点P，该节点有一个左子节点L和右子节点R，怎么变成最大堆
     * 首先比较L和R的大小，假设L<R；子节点最大的R再和P比较,如果P大，则本身就是最大堆，如果R大，则只需将P和R互换即可
     *
     * 拓展：如果P有左右子树，且左右子树都是最大堆，此时如何调整？和简单模型思想一致；P和左右子节点比较，P小就和最大的子节点互换
     * 然后如果P还有子节点，就继续比较，直到P比左右子节点都大为止
     */
    public static void adjustHeap(int[] array, int parent, int len) {
        int temp = array[parent];

        // child=2*parent+1,表示parent结点的左子节点，child+1表示parent结点的右子节点
        // 如果child<len，表示左子节点存在
        for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) {
            // 左子节点和右子节点相比较
            if (child + 1 < len && array[child] < array[child + 1]) {
                // 如果右子节点大，child指向右子节点
                // 此时child指向左右子节点中最大的那个节点
                child++;
            }
            // 子节点与父节点值temp相比较，如果子节点大
            if (temp < array[child]) {
                // 把较大值赋值给当前结点
                array[parent] = array[child];
                //parent指向子节点，parent不配当父节点，向下移动，如果还不配，继续向下
                parent = child;
            } else {
                break;
            }
        }
        // 当 for 循环结束后，我们已经将以 i 为父结点的树的最大值，放在了 最顶(局部)
        // 注意这里是局部的，该方法还没有完全将二叉树构成大顶堆
        // 所以调用该方法时，需要从叶子结点的父节点向上循环调用，将最大值类似冒泡一样推上去
        // 此时的parent不一定是入参时的parent，他可能往子节点或者说往下进行了移动
        array[parent] = temp;
    }

    /**
     * 元素交换
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array,int i,int j){
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
}
